package leetcode;

import java.util.*;

public class tree2 {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {
        TreeNode l = new TreeNode(0, null, null);
        TreeNode r = new TreeNode(2, null, null);
        TreeNode T = new TreeNode(1, l, r);
        preVisit(T);
        System.out.println();
        inVisit(T);
        System.out.println();
        lastVisit(T);
    }
    /**
     * 迭代法实现树的三种遍历方式
     */
    public static void preVisit(TreeNode tree){
        if(tree == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(tree);
        while(!stack.isEmpty()){
            TreeNode t = stack.pop();
            System.out.print(t.val + " ");
            if(t.right != null)
                stack.push(t.right);
            if(t.left != null)
                stack.push(t.left);
        }
    }


    public static void inVisit(TreeNode tree){
        if(tree == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = tree;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            cur = node.right;
        }
    }


    public static void lastVisit(TreeNode tree){
        if(tree == null)
            return;
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(tree);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.left != null)
                stack.push(node.left);
            if(node.right != null)
                stack.push(node.right);
        }
        Collections.reverse(list);
        System.out.println(list);
    }
}
